package com.bichengcao.googlecodejam.qualification2010;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class ThemePark {

	static int N;

	public static void main(String[] args) throws IOException {
		Input[] inputs = parseInput("src/com/bichengcao/googlecodejam/qualification2010/C-large.in");
		Output[] outputs = process(inputs);
		writeOutput("src/com/bichengcao/googlecodejam/qualification2010/ThemePark.out", outputs);
	}

	static class Input {
		int r;
		int k;
		int n;
		int[] g;
	}

	static class Output {
		long y;
	}
	
	private static Input[] parseInput(String filename) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader(filename));
		N = Integer.parseInt(in.readLine());
		Input[] array = new Input[N];

		for (int i = 0; i < N; i++) {
			Input input = array[i] = new Input();
			StringTokenizer st = new StringTokenizer(in.readLine());
			input.r = Integer.parseInt(st.nextToken());
			input.k = Integer.parseInt(st.nextToken());
			input.n = Integer.parseInt(st.nextToken());
			input.g = new int[input.n];
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < input.n; j++) {
				input.g[j] = Integer.parseInt(st.nextToken());
			}
		}

		in.close();
		return array;
	}

	private static Output[] process(Input[] inputs) {
		Output[] outputs = new Output[N];
		for (int i = 0; i < N; i++) {
			outputs[i] = process(inputs[i]);
		}
		return outputs;
	}

	private static Output process(Input input) {
		Output output = new Output();

		int[] q = new int[input.n];
		long[] s = new long[input.n + 1];
		int[] c = new int[input.n];
		int p = 0;
		int count = 0;
		long sum = 0;
		while (q[p] == 0) {
			int t = p;
			q[t] = input.g[p];
			p = (p + 1) % input.n;
			while (t != p && q[t] + input.g[p] <= input.k) {
				q[t] += input.g[p];
				p = (p + 1) % input.n;
			}
			sum += q[t];
			c[t] = count;
			s[++count] = sum;
		}
		sum += ((input.r - c[p]) / (count - c[p]) - 1) * (s[count] - s[c[p]]);
		sum += s[(input.r - c[p]) % (count - c[p]) + c[p]] - s[c[p]];
		output.y = sum;
		
//		sum = 0;
//		p = 0;
//		for (int i = 0; i < input.r; i++) {
//			int t = p;
//			int ts = input.g[p];
//			p = (p + 1) % input.n;
//			while (t != p && ts + input.g[p] <= input.k) {
//				ts += input.g[p];
//				p = (p + 1) % input.n;
//			}
//			sum += ts;
//		}
//		if (sum != output.y) {
//			System.out.println(input.r + " " + input.k);
//		}
		
		return output;
	}

	private static void writeOutput(String filename, Output[] outputs) throws IOException {
		PrintWriter out = new PrintWriter(new FileWriter(filename));
		for (int i = 0; i < N; i++) {
			Output output = outputs[i];
			out.println("Case #" + (i + 1) + ": " + output.y);
		}
		out.close();
	}

}
